package org.labuladong.动态规划算法.一维DP;

import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-19:43
 * @Description:
 * @version: 1.0
 */
public class LC_面试题_马戏团人塔 {

	public static void main(String[] args) {
//		int[] height = {65,70,56,75,60,68};
//		int[] weight = {100,150,90,190,95,110};
		int[] height = {1,2,2,2,3};
		int[] weight = {4,5,6,7,8};
		System.out.println(bestSeqAtIndex(height, weight));
	}

	public static int bestSeqAtIndex(int[] height, int[] weight) {

		int[][] envelopes = new int[height.length][2];
		for (int i = 0; i < height.length; i++) {
			envelopes[i][0] = height[i];
			envelopes[i][1] = weight[i];
		}
		return maxEnvelopes(envelopes);
	}

	public static int maxEnvelopes(int[][] envelopes) {
		if (envelopes.length == 0)
			return 0;

		// 根据宽度和高度对信封进行排序,升序排列
		Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

		// 初始化动态规划数组
		int[] dp = new int[envelopes.length];
		int maxLength = 0;

		for (int i = 0; i < envelopes.length; i++) {
			int width = envelopes[i][0], height = envelopes[i][1];
			// 二分查找找到当前信封可以嵌套的最大信封
			int j = binarySearch(dp, 0, maxLength, height);
			// 如果没有找到可以嵌套的信封，当前信封可以作为一个新的起点
			if (j == maxLength) {
				maxLength++;
			}
			// 更新动态规划数组
			dp[j] = width;
		}

		return maxLength;
	}

	private static int binarySearch(int[] dp, int start, int end, int target) {
		// 当start和end指针没有相遇时，继续进行二分查找
		while (start < end) {
			// 计算中间位置的索引
			int mid = start + (end - start) / 2;

			// 如果中间位置的信封高度小于目标高度，说明我们要找的位置在右半边
			if (dp[mid] < target) {
				start = mid + 1;
			}
			// 如果中间位置的信封高度大于或等于目标高度，说明我们要找的位置在左半边或就是中间位置
			else {
				end = mid;
			}
		}
		// 返回在dp数组中第一个大于或等于target的位置的索引
		// 如果整个数组中的所有信封高度都小于target，则start将等于end，返回start即可
		return start;
	}

}
